home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / edit / me_cd25.zip / DOC.ZIP / UNDO.ART < prev   
Text File  |  1992-11-09  |  28KB  |  672 lines
  1. -*-text-*-
  2.  
  3.  
  4.           Implementing Undo for Text Editors
  5.           ------------ ---- ---    ---- -------
  6.  
  7.                 Craig Durland
  8.                craig@cv.hp.com
  9.                 Copyright 1991
  10.  
  11.  
  12.                 February 1991
  13.                    Revised
  14.                September 1991   
  15.                 February 1992
  16.  
  17.  
  18. Probably anyone who has used a text editor has, at one time or another,
  19. made a boo boo and immediately wished they could to go back in time and
  20. not do it all over again.  The Undo command gives that ability by moving
  21. backwards in time, reversing the effects of the most recent changes to
  22. the text.  Some undo commands can go back to the beginning of time,
  23. undoing all changes that have occurred to the text.
  24.  
  25. The undo described in this article is a subset of the idealized undo -
  26. it only reverses changes to text.  It doesn't keep track of cursor
  27. movements, buffer changes or the zillions of other things we do while
  28. editing text.  While this can make undoing changes disconcerting because
  29. it can jump from change to change differently from what you remember, it
  30. also reduces the amount of stuff that the editor needs to remember
  31. (saving memory) and helps keep the editor from bogging down trying to
  32. keep track of whats been going on.  Finally, the material presented is
  33. for text editors.  Editors of other types may find some of the
  34. discussion relevant but that will be a happy accident.
  35.  
  36. Jonathan Payne (author of JOVE) has stated that "Undo/redo is trivial to
  37. implement" (comp.editors, Tue, 2 Jan 1990).  Having just implemented
  38. undo for the editor I am working on, I think that straight forward is a
  39. better term than trivial.  Since it took me a long time to figure out a
  40. workable undo scheme, I thought others might be interested in what I
  41. did.
  42.  
  43.  
  44.  
  45. Caveats:  The algorithms, code and data structures used in this article
  46. are based on working and tested code that has been "sanitized" to remove
  47. obscuring details (like what stack data structures I used).  If you use
  48. the code, make sure you understand it so that you can properly fill in
  49. the missing details.
  50.  
  51. Conditions:  You are free to use the algorithms, code and data
  52. structures contained in this article in anyway you please.  If you use
  53. large chunks, I would appreciate an acknowledgment.  If you distribute
  54. this article, in whole or part, please retain the authorship notice.
  55.  
  56.  
  57.  
  58.             What is Not Discussed
  59.             ---- --    --- ---------
  60.  
  61. Redo is a undo for undo.  Very handy if you undo one time to many and
  62. need to undo that last undo.  I haven't implemented it yet but I think
  63. that it will be easy to modify the algorithms to support it.  I also
  64. think some dragons are there but they are hiding from me.  We'll see
  65. when I actually get around to doing it.
  66.  
  67.  
  68.  
  69.        Editor Implementations and How They Affect Undo
  70.        ------ --------------- --- --- ---- ------ ----
  71.  
  72. Two popular ways text editors store text are "buffer gap" and "linked
  73. list of lines" (described in detail else where - see comp.editors).  As
  74. you might imagine, different implementations for storing text can affect
  75. undo implementations.  Fortunately for this article, the affects are
  76. relatively minor.  As I discuss data structures and algorithms, I will
  77. point out the differences.
  78.  
  79. Note:  I will refer to buffer gap editors as BGE and linked list editors
  80. as LLE.
  81.  
  82.  
  83.            What You Need to Save to Implement Undo
  84.            ---- ---    ---- --    ---- --    --------- ----
  85.  
  86. I use Undo Events to represent text changes.  These events are kept in a
  87. undo stack, most recent event at the top of the stack.  There is one
  88. stack per text object (buffer in Emacs) so undo can only track changes
  89. on a per buffer basis.  This simplifies things quite a bit over tracking
  90. all changes globally in a multibuffer editor.
  91.  
  92. I found that four event types seem to be enough describe all text
  93. changes.  They are:
  94. - BU_INSERT:  This event is used when text is inserted.  The most common
  95.   case is when you type.  When text is inserted, we need to remember how
  96.   much was inserted and where it was inserted.  We don't need to
  97.   remember the what the text was because to undo this type of event, all
  98.   we have to do is delete the inserted text.  Note that in order to
  99.   reduce the number of events saved (and memory used), you need to be
  100.   able to detect text that is inserted sequentially (like when you type
  101.   "123") so that all these events can packed into one event.  This can
  102.   affect more than you would think at first glance and will be discussed
  103.   more fully else where.
  104.  
  105. - BU_DELETE:  This event is used when text is deleted, for example when
  106.   you use the delete (or backspace) key.  Here we need to remember the
  107.   place where the deletion took place and the text to be deleted.  Note
  108.   that we have to save the text before (or while) it is deleted.  This
  109.   is can cause trouble for some editor implementations.  Again, event
  110.   packing can save much of space if users like to lean on the delete
  111.   key.  To undo a delete, we have to insert the deleted text at the
  112.   place where it was deleted.
  113.  
  114. - BU_SP:  A sequence point is a stopping point in the undo stack.  It
  115.   tells the undo routine that this is the last event to undo so the user
  116.   will think that one of his actions has been undone.  Note that this
  117.   implies that one user action may cause one or (many) more undo events
  118.   to be saved.  This is especially true when the editor supports macros
  119.   or an extension language.  I think that it is important that one press
  120.   of the undo key undoes one user action (there are a few exceptions
  121.   (like query replace)).  Probably one of the hardest things to "get
  122.   right" (from the users point of view) is where to place sequence
  123.   points.  Here is my list of rules for sequence points (take these with
  124.   a grain of salt - these are my opinions with nothing to back them up.
  125.   They may change.):
  126.   - Need sequence points so undoing stops at "natural, expected" places.
  127.   - Undo should stop where user explicitly marked the buffer as
  128.     unchanged (like save buffer to disk).  These are usually UNCHANGED
  129.     events.
  130.   - A string of self insert keys should undo as one.  Its pretty
  131.     annoying to have to hit undo 14 times to undo "this is a test".
  132.   - A word wrap or Return should break a character stream.  Thus undo
  133.     only backs up a line at at time, probably better than undoing an
  134.     entire paragraph when only one line needed undoing.
  135.   - Commands, macros, programs written in the extension language, etc
  136.     should undo as a unit.  ie if pressing a key caused a bunch of stuff
  137.     to happen, pressing undo should undo all the stuff the key caused.
  138.   - Since rules can't cover all cases (like query replace), programs
  139.     need to be able to add sequence points.
  140.  
  141.   I also store the buffer modified state here so I know to mark the
  142.   buffer as unchanged if it was before this change happened.
  143.  
  144. - BU_UNCHANGED:  This event marks a time when the text was marked as
  145.   unchanged or saved.  Examples include saving the text to the disk.
  146.   When undoing, this event marks a stopping point:  The user has undoed
  147.   back to a time when the buffer was "safe".  When you make an
  148.   inadvertent change to text that you only wanted to look at, it is
  149.   psychologically reassuring to know the text is back to its original
  150.   state.
  151.  
  152.   Only the most recent unchanged event actually indicates that the
  153.   buffer contents match those out on the disk (and every buffer change
  154.   before and after that event means the buffer is out of sync with the
  155.   disk).  For undo, this means that only the most recent unchanged event
  156.   is valid - when that event is undone, the buffer matches the disk.
  157.   After that one, other unchanged events need to be ignored because the
  158.   buffer at that point can't match the disk.
  159.  
  160.   Note that BU_UNCHANGED events are really just special cases of
  161.   sequence points.  You could easily just combine them into one event.
  162.  
  163. It should be obvious by now that much editing would generate a LOT of
  164. undo events.  Unless your computer has an infinite amount of memory, you
  165. need some rules about when to start throwing away events.  Since
  166. different people will have different ideas about th